package promote.brozen.algorithm.tree.binary.rbt;

import promote.brozen.algorithm.tree.Tree;
import promote.brozen.algorithm.tree.binary.RecursionBinaryTreeWalker;

import java.util.Objects;
import java.util.function.Consumer;

/**
 * 红黑树 Red Black Tree
 * 性质1：每个节点要么是黑色，要么是红色。
 * 性质2：根节点是黑色。
 * 性质3：每个叶子节点（NIL）是黑色。
 * 性质4：每个红色结点的两个子结点一定都是黑色。
 * 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
 *
 * 根据性质4，可以推导，不存在连续的两个父子节点都为红色；
 * 根据性质5，可以推导，如果一个节点有一个黑色子节点，则其另一个子节点必定存在；
 *
 * 算法导论中，定义了一种 松弛红黑树，只满足红黑树性质1、3、4、5，即根节点不为红的红黑树；
 *
 *
 * @author Brozen
 * @date 2020/1/2 5:33 PM
 */
public class RBTTree<K extends Comparable<K>> implements Tree<K> {

    private final RBTTreeNode<K> Nil;

    private RBTTreeNode<K> root;

    public RBTTree() {
        Nil = new RBTTreeNode<>(null);
        Nil.setLeftChild(Nil);
        Nil.setRightChild(Nil);
        Nil.setColor(RBTTreeNode.Color.BLACK);
        this.root = Nil;
    }

    @Override
    public void add(K key) {
        key = Objects.requireNonNull(key);
        RBTTreeNode<K> insertionNode = doAdd(key);

        if (insertionNode != Nil) {// 返回Nil说明是更新操作，无需平衡
            /*
             * 插入之后，需要考虑是否会违反红黑树性质，违反了需要通过平衡来保持性质；
             * 引入的新节点是红色，如果父节点是黑色，不会违反任何性质；但如果父节点是红色，会违反性质4；
             * 开始进行平衡时，将新增的节点视为平衡节点；
             */
            RBTTreeNode<K> parent = insertionNode.getParent();
            if (parent != Nil && !parent.isBlack()) {
                doAddBalance(insertionNode);
                // 有可能平衡后，根节点被旋转到了其他位置，需要重设下根节点
                while (this.root.getParent() != Nil) this.root = this.root.getParent();
            }
        }

        if (!this.root.isBlack()) {
            this.root.setColor(RBTTreeNode.Color.BLACK);
        }
    }

    private RBTTreeNode<K> doAdd(K key) {
        RBTTreeNode<K> parent = Nil;
        RBTTreeNode<K> node = this.root;
        int result = 0;

        // 自顶向下 找到新节点的插入位置
        while (node != Nil) {
            result = node.getKey().compareTo(key);
            if (result > 0) {
                parent = node;
                node = node.getLeftChild();
            } else if (result < 0) {
                parent = node;
                node = node.getRightChild();
            } else {
                break;
            }
        }

        if (node != Nil) {
            // 找到一个相等的节点，是更新操作
            node.setKey(key);
            node = Nil;
        } else {
            // 插入新节点
            node = new RBTTreeNode<>(key);
            node.setLeftChild(Nil);
            node.setRightChild(Nil);

            if (parent != Nil) {
                node.setParent(parent);
                if (result > 0) {
                    parent.setLeftChild(node);
                } else if (result < 0) {
                    parent.setRightChild(node);
                }
            }
            if (this.root == Nil) {
                this.root = node;
                this.root.setParent(Nil);
            }
        }

        return node;
    }

    /**
     * 新增操作的平衡，只会违反性质4，即出现了父子节点连续为红色的情况；
     * 在新增平衡操作中，以红色子节点为平衡节点，平衡节点的父节点为红色，从平衡节点开始 自底向上 进行平衡；
     *   * 根据性质5可以推导出，父节点为红色时，祖父节点必定为黑色；
     *
     *   需要解决性质4，有两种考虑：
     *      1.让红色节点移动到平衡节点的兄弟节点位置(旋转)，这种方法不影响黑高；
     *      2.让平衡节点或其父节点其中一个节点染黑；这种会影响黑高，破坏了性质5；
     *
     *   优先考虑一下不破坏性质5的方法1，使用这种方法的话，旋转完之后，原叔叔节点的父节点会变成一个红色节点，原叔叔节点为红色时会影响性质4；
     *   在考虑一下方法2，平衡节点或父节点其中一个染黑后，以父节点为根的子树黑高+1，影响整棵树性质5；补救办法是让以祖父节点为根的子树黑高-1，此时不影响整棵树性质；
     *      但是以祖父节点为根的子树黑高-1后，"父节点的兄弟节点(叔叔节点)为根"的子树黑高比"以父节点为根的子树"黑高少1，又要想办法让"叔叔节点为根的子树"黑高+1；
     *      若此时叔叔节点为红色，只要将叔叔节点染黑就能实现"叔叔节点为根的子树"黑高+1；
     *   方法1适用与叔叔节点为黑色时，方法2适用与叔叔节点为红色时，nice，刚好互补。
     *
     * 因此分类讨论(暂时只考虑平衡节点是父节点左子节点、父节点是祖父节点左子节点的情况，其他情况可以通过旋转得到这种或者与这种对称的情况)：
     *   情况1：叔叔节点颜色为红色；
     *       将父节点、叔叔节点染黑，祖父节点染红，目标a、b、c均能实现，平衡结束；
     *       但此时祖父节点由黑变红，如果祖父节点的父节点是红色，会违反性质4，又需要以祖父节点为平衡节点再次进入平衡操作(递归)；
     *   情况2：叔叔节点颜色为黑色；(叔叔节点为Nil时也是黑色)
     *     情况2.1 平衡节点的父节点，是祖父节点的左子节点；
     *       情况2.1.1 平衡节点是父节点的右子节点；
     *         此时，让父节点左旋，平衡节点设置为原父节点，父节点设置为原平衡节点，得到情况2.1.2；
     *                GP-B                     GP-B                     GP-B
     *               /   \       GP右旋       /    \      重新赋值       /   \
     *             P-R   U-B    -------->   B-R   U-B    -------->    P-R   U-B
     *               \                     /                         /
     *              B-R                   P-R                       B-R
     *       情况2.1.2 平衡节点是父节点的左子节点
     *         此时让祖父节点右旋，祖父节点染红，父节点染黑；这一波操作完成后，平衡节点与原祖父节点在同一层均为红色，
     *         父节点为黑色，占据原祖父节点的位置，不会向上影响性质4；又因为黑高不变，不影响整棵树性质5；此时平衡完成，可以退出了;
     *         B:平衡节点 P:父节点 GP:祖父节点 U:叔叔节点    后缀 R:红色 B:黑色
     *                GP-B                     P-R                       P-B
     *               /   \       GP右旋       /    \         变色        /   \
     *             P-R   U-B    -------->   B-R   GP-B    -------->   B-R  GP-R
     *            /                                 \                        \
     *          B-R                                U-B                      U-B
     *     情况2.2 平衡节点的父节点，是祖父节点的右子节点；
     *       情况2.2.1 平衡节点是父节点的左子节点；
     *         父节点右旋，平衡节点设置为原父节点，父节点设置为原平衡节点，得到2.2.2；
     *       情况2.2.2   平衡节点是父节点的右子节点
     *         此时让祖父节点左旋，祖父节点染红，父节点染黑；
     *         该情况是2.1.2的对称，操作完成之后性质5得到保持，可以退出平衡；
     */
    private void doAddBalance(RBTTreeNode<K> node) {
        if (node == Nil) {
            return;
        }
        if (node == this.root) {
            node.setColor(RBTTreeNode.Color.BLACK);
            return;
        }

        // 自底向上平衡过程中，如果平衡节点的父节点为Nil，说明平衡节点应该是根节点
        // 又因为平衡节点可能是经过旋转后的，此时需要重新为根节点指针赋值
        RBTTreeNode<K> parent = node.getParent();
        if (parent == Nil) {
            this.root = node;
            return;
        }

        RBTTreeNode<K> grandParent = parent.getParent();
        RBTTreeNode<K> uncle;
        if (parent.isLeftChildOfParent()) {
            uncle = grandParent.getRightChild();
        } else {
            uncle = grandParent.getLeftChild();
        }

        if (uncle != Nil && !uncle.isBlack()) {
            // 情况1：叔叔节点存在，且为红色；
            //   将父节点与叔节点都设置为黑色；祖父节点设置为红色；然后将祖父节点作为平衡节点递归处理；
            parent.setColor(RBTTreeNode.Color.BLACK);
            uncle.setColor(RBTTreeNode.Color.BLACK);
            // 父节点叔叔节点为红，根据性质4祖父节点必定为黑，且必定存在
            grandParent.setColor(RBTTreeNode.Color.RED);
            RBTTreeNode<K> grandParentParent = grandParent.getParent();
            if (!grandParentParent.isBlack()) {
                doAddBalance(grandParent);
            }
        } else {
            // 情况2：叔叔节点为黑色
            if (parent.isLeftChildOfParent()) {
                // 情况2.1：平衡节点的父节点，是祖父节点的左子节点时
                if (node.isRightChildOfParent()) {
                    // 情况2.1.1：平衡节点是父节点的右子节点，则先将父节点左旋，到左左结构(情况2.1.2)
                    parent = rotateLeft(parent);
                }

                // 情况2.1.2：平衡节点是父节点的左子节点，将父节点这个红色借到叔叔节点那边
                // 操作是父节点染黑、祖父节点染红，祖父节点右旋
                parent.setColor(RBTTreeNode.Color.BLACK);
                // 这里祖父节点不可能为空，证明如下：
                //   若祖父节点为空，则父节点为根节点；若父节点为根节点，则父节点就是黑色，不会进入到这个平衡过程中；
                grandParent.setColor(RBTTreeNode.Color.RED);
                rotateRight(grandParent);
            } else if (parent.isRightChildOfParent()) {
                // 情况2.2：平衡节点的父节点，是祖父节点的右子节点
                if (node.isLeftChildOfParent()) {
                    // 情况2.2.1：平衡节点是父节点的左子节点，先将父节点右旋，到右右结构(情况2.2.2)
                    parent = rotateRight(parent);
                }

                // 情况2.2.2：平衡节点是父节点的右子节点
                // 父节点染黑、祖父节点染红，祖父节点左旋
                parent.setColor(RBTTreeNode.Color.BLACK);
                grandParent.setColor(RBTTreeNode.Color.RED);
                rotateLeft(grandParent);
            }
        }
    }

    /**
     *     A                    B
     *    / \                  / \
     *   B   C   右旋之后为    D   A
     *  / \                     / \
     * D   E                   E   C
     */
    private RBTTreeNode<K> rotateRight(RBTTreeNode<K> A) {
        if (A == Nil) {
            return Nil;
        }

        RBTTreeNode<K> P = A.getParent();
        Boolean isLeftSubTree = P == Nil ? null : P.getLeftChild() == A;

        RBTTreeNode<K> B = A.getLeftChild();
        RBTTreeNode<K> E = B.getRightChild();

        A.setLeftChild(E);
        E.setParent(A);

        B.setRightChild(A);
        B.setParent(A.getParent());
        A.setParent(B);

        if (isLeftSubTree != null) {
            if (isLeftSubTree) {
                P.setLeftChild(B);
            } else {
                P.setRightChild(B);
            }
        }

        return B;
    }

    /**
     *     A                        C
     *    / \                      / \
     *   B   C    左旋之后为       A   E
     *      / \                 / \
     *     D  E                B   D
     *
     * 旋转后，自动建立C与其父节点的关系
     */
    private RBTTreeNode<K> rotateLeft(RBTTreeNode<K> A) {
        if (A == Nil) {
            return Nil;
        }

        RBTTreeNode<K> P = A.getParent();
        Boolean isLeftSubTree = P == Nil ? null : P.getLeftChild() == A;

        RBTTreeNode<K> C = A.getRightChild();
        RBTTreeNode<K> D = C.getLeftChild();

        A.setRightChild(D);
        if (D != Nil) {
            D.setParent(A);
        }

        C.setLeftChild(A);
        C.setParent(A.getParent());
        A.setParent(C);

        if (isLeftSubTree != null) {
            if (isLeftSubTree) {
                P.setLeftChild(C);
            } else {
                P.setRightChild(C);
            }
        }

        return C;
    }

    @Override
    public void remove(K key) {
        this.doRemove(this.searchNode(this.root, key));
        // 有可能平衡后，根节点被旋转到了其他位置，需要重设下根节点
        while (this.root.getParent() != Nil) this.root = this.root.getParent();
    }

    private void doRemove(RBTTreeNode<K> node) {
        if (node == Nil) {
            // node为空，说明没找到接口，返回
            return;
        }

        if (node.getLeftChild() == Nil && node.getRightChild() == Nil) {
            // 是叶子节点，需要删除该节点；
            // 如果该节点为红色，直接删除就行；但如果为黑色，则先让该节点参与平衡，平衡完之后再删除
            if (node.isBlack()) {
                // 是黑色，先平衡
                this.doDeleteBalance(node);
            }

            // 执行删除
            if (node.isLeftChildOfParent()) {
                node.getParent().setLeftChild(Nil);
            } else if (node.isRightChildOfParent()) {
                node.getParent().setRightChild(Nil);
            } else {
                // 父节点为空，删除的是根节点
                this.root = Nil;
            }
        } else if (node.getLeftChild() == Nil) {
            // 左子节点为空，用右子节点代替待删除节点，然后删除右子节点
            RBTTreeNode<K> rc = node.getRightChild();
            node.setKey(rc.getKey());
            this.doRemove(rc);
        } else if (node.getRightChild() == Nil) {
            // 右子节点为空，用左子节点代替待删除节点，然后删除左子节点
            RBTTreeNode<K> lc = node.getLeftChild();
            node.setKey(lc.getKey());
            this.doRemove(lc);
        } else {
            // 两个子节点都存在，找前驱节点（左子树的最大节点），用前驱代替待删除节点，然后删除前驱节点
            RBTTreeNode<K> successor = min(node.getLeftChild());
            node.setKey(successor.getKey());
            this.doRemove(successor);
        }
    }

    private void doDeleteBalance(RBTTreeNode<K> node) {
        if (node.isLeftChildOfParent()) {
            doDeleteBalanceAsLeftSubNode(node);
        } else if (node.isRightChildOfParent()) {
            doDeleteBalanceAsRightSubNode(node);
        }
    }

    /**
     * 一个没啥卵用的性质推导-借红色节点：
     * 一个节点的左子节点是红色，如何把右子节点变为红色(把红色节点从左边借到右边)？
     *      交换左子节点与父节点颜色，然后父节点右旋；
     * 一个节点的右子节点是红色，如何把左子节点变为红色(把红色节点从右边借到左边)？
     *      交换右子节点与父节点颜色，然后父节点左旋；
     *
     *
     *
     * 平衡节点是父节点的左子节点时
     *
     * 删除平衡操作时，要处理的情况是平衡节点为根的子树(此情况下是父节点左子树)黑高-1，此时会违反性质5；
     * 为了保持性质5，要达到两个目的：
     *      1. 首先要保证父节点的左右子树黑高相等；情况是父节点左子树黑高+1 或 父节点右子树黑高-1；
     *      2. 其次是保持父节点为根的子树黑高不变；
     *          如果能做到，则性质5得到保持，平衡完成退出；
     *          如果保证不了，父节点为根的子树黑高应该是会-1，此时将父节点作为平衡节点再次递归进入平衡操作；
     *      * 首先明确黑高变化的方式：黑高-1可以通过黑色节点染红实现，黑高+1可通过红色节点染黑实现；
     *
     * 为了达到目的1，我们有两种手段，
     *   1.父节点左子树黑高+1；这种手段不光能达到目的1，左子树黑高+1后，父节点满足性质5且黑高不变，目的2也满足了，此时就可以退出平衡操作；
     *   2.父节点右子树黑高-1；这种手段只能达到目的1，目的2达不到，需要把父节点递归进入平衡操作；
     * 所以优先考虑使用"父节点左子树黑高+1"的方式，也就是让平衡节点为根的子树黑高+1；
     * 这里让左子树黑高+1的实现方法的思想是：从兄弟节点那边借一个红色节点来，然后把红色节点染黑，黑高就+1了；
     *
     * 树图标记说明
     * B: 平衡节点 P:父节点 U:叔叔节点 S:兄弟节点 SL:兄弟节点左子节点 SR:兄弟节点右子节点
     * 后缀 R:红色节点 B:黑色节点  ?:颜色任意
     * 后缀 (i) (i-1) (i+1) :黑高
     *
     * 情况1. 如果平衡节点是红色，那么直接变黑就行；父节点左子树黑高+1，达到了目的1、2；
     * 情况2. 如果平衡节点是黑色，且平衡节点为根的子树是一颗松弛红黑树，为了让整棵子树黑高+1，最好的情况是在平衡节点前加入一个红色节点，然后把红色节点染黑；
     * 那这个红色节点不可能凭空插入，就要从原有的树中拿到，平衡节点为根的子树上没有，可以考虑从平衡节点的兄弟节点子树上借；
     *   情况2.1 兄弟节点为红色；兄弟节点为红色，则通过旋转与变色把兄弟节点从父节点右子树借到父节点左子树上来；
     *          把兄弟节点借过来之后，平衡节点的兄弟节点是原兄弟节点的左子节点；此时兄弟节点黑高比平衡节点黑高多1；这时候变成了情况2.4中父节点换颜色为红的子情况；
     *          这不就是刚推导出来的借红色节点的方法；
     *              P-B(i+1)                                    S-B(i+1)         借来的            S-B(i+1)
     *             /      \           借一下红色                 /      \         红色变色           /      \
     *       B-B(i-1)   S-R(i)     -------------->          P-R(i)    SR-B(i)  --------->      P-B(i)   SR-B(i)
     *                  /    \                              /    \                            /     \
     *           SL-B(i)   SR-B(i)                    B-B(i-1)  SL-B(i)                 B-B(i-1)  SL-R(i-1)
     *           初始2.1情况                                到2.4情况                          2.4情况处理之后，达到平衡
     *
     *   情况2.2 兄弟节点为黑色，兄弟节点的右子节点为红色，左子节点为黑色；把右子节点的红色借过来，同时保持父节点黑高不变；
     *          要怎么借？首先肯定是通过P节点左旋，才能使兄弟节点的子节点到平衡节点这边来，先左旋一下，看看左旋之后的数结构；
     *          下图可以看到，P左旋之后，平衡节点的兄弟节点变成原兄弟节点的左子节点，且这个新兄弟的黑高和平衡节点黑高一样，都是-1的；
     *          为了不影响向上的性质五，需要让旋转之后的P、SR节点黑高为i，S位置黑高和原来一样为?(由节点颜色决定)；
     *          所以，交换P和S的颜色，则P的黑高为i，P的两个子节点黑高为i-1，此时P为根的子树满足松弛红黑树；
     *               将SR染黑，则SR的黑高从i-1变为i，P和SR黑高都为i，S为根的节点满足松弛红黑树；
     *          而且经过上面的变化之后，S颜色还是?，黑高也不变，S向上不影响性质5，S为黑向上也不会影响性质4，平衡结束；
     *              P-?(?)                              S-B()                               S-?(?)
     *             /     \             P左旋           /     \             染色后            /     \
     *       B-B(i-1)   S-B(i)    -------------->   P-?()   SR-R(i-1) ------------->    P-B(i)   SR-B(i)
     *                 /     \                     /    \                               /    \
     *          SL-?(i-1)   SR-R(i-1)        B-B(i-1)  SL-?(i-1)                  B-B(i-1)  SL-?(i-1)
     *          初始2.2情况                         P左旋之后                               染色后达到平衡，可以退出了
     *
     *   情况2.3 兄弟节点为黑色，兄弟节点的右子节点为黑色，左子节点为红色；
     *          这里首先想到的还是从兄弟节点借红色，借节点的话，考虑P左旋；先看一下根据2.2的思路，左旋变色之后的结构；
     *          可以看到，P左旋变色后，P子树是满足松弛红黑树了，但SR节点黑高是i-1，少了，有两种处理办法：
     *              方法1. 将SR作为新的平衡节点，递归带入平衡流程；
     *              方法2. 将P节点染红，这样S节点黑高-1，将S递归带入平衡流程；
     *          方法1可以自己试一下，其实就是情况2.3的对称的情况，采用这种方式处理，在对称的处理逻辑里又会转换为情况2.3，死循环了；
     *          方法2相当于继续向上平衡，并没有借到右子树的红色节点，反而多了一个红色节点，并不是最优解；
     *          综上来看，要借到SL这个红色节点，单纯的旋转P做不到，因为SR颜色未知，P左旋之后，不能保证一定可以通过变色让SR黑高+1；
     *          所以，如果能将SL这个红色节点变成S的右子节点，把情况转成2.2，就能实现平衡了，而且不需要再向上平衡；
     *              P-?(?)                           S-?()
     *             /     \           P左旋          /     \
     *       B-B(i-1)   S-B(i)       与变色     P-B(i)     SR-?(i-1)
     *                 /     \     -------->  /      \
     *          SL-R(i-1)  SR-?(i-1)     B-B(i-1)  SL-R(i-1)
     *
     *          根据上面的借红色节点的方法，交换SL与S的颜色，然后S节点右旋，即可把左边的红色节点(SL)借到右边来(S)；
     *          然后套用2.2的解法，把S这个节点的红色借到平衡节点所在子树去，就能在本次循环时实现平衡，不用向上再处理；
     *              P-?(?)                                       P-?(?)                                SL-?(?)
     *             /     \             根据没卵用性质             /     \                            /           \
     *       B-B(i-1)   S-B(i)       将SL和S换色，S右旋     B-B(i-1)   SL-B(i)       套用2.2      P-B(i)          S-B(i)
     *                 /     \     -------------------->            /      \    ------------>  /   \            /     \
     *          SL-R(i-1)  SR-?(i-1)                        SLL-?(i-1)   S-R(i-1)      B-B(i-1) SLL-?(i-1) SLR-?(i-1) SR-?(i-1)
     *          /       \                                               /       \
     *   SLL-?(i-1)   SLR-?(i-1)                                 SLR-?(i-1)   SR-?(i-1)
     *
     *   情况2.4 兄弟节点为黑色，兄弟节点的两个子节点也都为黑色；按照上面的思路，这里没办法从兄弟节点再借子节点过来了，只能放弃实现目的2，保证目的1；
     *          将兄弟节点颜色设置为红色，使兄弟节点和平衡节点黑高都-1，则父节点的黑高-1，这时候将父节点作为平衡节点递归带入平衡操作；
     *              P-?(?)                                      P-?(?-1)
     *             /     \          兄弟节点染红，黑高-1          /     \
     *       B-B(i-1)   S-B(i)      ----------------->   B-B(i-1)    S-R(i-1)
     *                 /    \                                       /       \
     *          SL-B(i-1)   SL-B(i-1)                        SL-B(i-1)   SR-B(i-1)
     */
    private void doDeleteBalanceAsLeftSubNode(RBTTreeNode<K> node) {
        // 情况1 平衡节点为红色，直接设置为黑色，完成平衡；
        if (!node.isBlack() || node == this.root) {
            node.setColor(RBTTreeNode.Color.RED);
            return;
        }

        RBTTreeNode<K> parent = node.getParent();
        RBTTreeNode<K> sibling = parent.getRightChild();
        RBTTreeNode<K> siblingLeft = sibling.getLeftChild();
        RBTTreeNode<K> siblingRight = sibling.getRightChild();
        if (!sibling.isBlack()) {
            // 情况2：平衡节点为黑色，兄弟节点为红色；通过借红色方法，把兄弟节点的红色借到平衡节点这边
            // 兄弟节点为红色，则将父节点与兄弟节点交换颜色，然后父节点左旋，将情况转换为兄弟节点为黑色(情况2)
            // 兄弟节点为红色，根据性质4，父节点、兄弟节点的子节点也都是黑色，所以将父节点染红，兄弟节点染黑
            parent.setColor(RBTTreeNode.Color.RED);
            sibling.setColor(RBTTreeNode.Color.BLACK);
            rotateLeft(parent);
            // 将借来的红色借到变色
            parent.setColor(RBTTreeNode.Color.BLACK);
            if (siblingLeft != Nil) {
                siblingLeft.setColor(RBTTreeNode.Color.RED);
            }
        } else if (sibling.isBlack()) {
            // 情况2：平衡节点为黑色，兄弟节点也为黑色；
            if (siblingLeft.isBlack() && siblingRight.isBlack()) {
                // 情况2.3 平衡节点黑色，兄弟节点黑色，兄弟节点两个子节点都是黑色；
                sibling.setColor(RBTTreeNode.Color.RED);
                doDeleteBalance(parent);
                return;
            }

            if (!siblingLeft.isBlack() && siblingRight.isBlack()) {
                // 情况2.2 平衡节点黑色，兄弟节点黑色，兄弟节点左子节点红色，右子节点黑色；
                siblingLeft.setColor(RBTTreeNode.Color.BLACK);
                sibling.setColor(RBTTreeNode.Color.RED);
                siblingRight = sibling;
                sibling = rotateRight(sibling);
            }

            // 情况2.1 平衡节点黑色，兄弟节点黑色，兄弟节点右子节点红色；
            rotateLeft(parent);
            sibling.setColor(parent.getColor());
            parent.setColor(RBTTreeNode.Color.BLACK);
            siblingRight.setColor(RBTTreeNode.Color.BLACK);
        }

    }

    /**
     * 上面的对称，也有四种情况
     * 情况1：平衡节点为红色；
     * 情况2：平衡节点为黑色，兄弟节点为红色；
     * 情况2.1：平衡节点为黑色，兄弟节点为黑色，兄弟节点左子节点为红色、右子节点颜色任意；
     * 情况2.2：平衡节点为黑色，兄弟节点为黑色，兄弟节点左子节点为黑色、右子节点为红色；
     * 情况2.3：平衡节点为黑色，兄弟节点为黑色，兄弟节点的子节点均为黑色；
     */
    private void doDeleteBalanceAsRightSubNode(RBTTreeNode<K> node) {
        // 情况1 平衡节点为红色
        if (!node.isBlack() || node == this.root) {
            node.setColor(RBTTreeNode.Color.BLACK);
            return;
        }

        RBTTreeNode<K> parent = node.getParent();
        RBTTreeNode<K> sibling = parent.getLeftChild();
        RBTTreeNode<K> siblingLeft = sibling.getLeftChild();
        RBTTreeNode<K> siblingRight = sibling.getRightChild();
        if (!sibling.isBlack()) {
            // 情况2 平衡节点为黑色，兄弟节点为红色
            sibling.setColor(RBTTreeNode.Color.BLACK);
            parent.setColor(RBTTreeNode.Color.RED);
            rotateRight(parent);
            // 旋转后变色
            parent.setColor(RBTTreeNode.Color.BLACK);
            if (siblingRight != Nil) {
                siblingRight.setColor(RBTTreeNode.Color.RED);
            }
        } else if (sibling.isBlack()) {
            // 情况2.3 平衡节点为黑色，兄弟节点为黑色，兄弟节点的子节点均为黑色
            if (siblingLeft.isBlack() && siblingRight.isBlack()) {
                sibling.setColor(RBTTreeNode.Color.RED);
                doDeleteBalance(parent);
                return;
            }

            // 情况2.2 平衡节点为黑色，兄弟节点为黑色，兄弟节点左子节点为黑色、右子节点为红色
            if (siblingLeft.isBlack() && !siblingRight.isBlack()) {
                sibling.setColor(RBTTreeNode.Color.RED);
                siblingRight.setColor(RBTTreeNode.Color.BLACK);
                siblingLeft = sibling;
                sibling = rotateRight(sibling);
            }

            // 情况2.1 平衡节点为黑色，兄弟节点为黑色，兄弟节点左子节点为红色、右子节点颜色任意
            rotateLeft(parent);
            sibling.setColor(parent.getColor());
            parent.setColor(RBTTreeNode.Color.BLACK);
            siblingLeft.setColor(RBTTreeNode.Color.BLACK);
        }
    }

    private RBTTreeNode<K> min(RBTTreeNode<K> node) {
        while (node.getLeftChild() != Nil) {
            node = node.getLeftChild();
        }

        return node;
    }

    @Override
    public K search(K key) {
        RBTTreeNode<K> node = searchNode(this.root, key);
        return node == Nil ? null : node.getKey();
    }

    private RBTTreeNode<K> searchNode(RBTTreeNode<K> node, K key) {
        if (node == Nil) {
            return Nil;
        }

        int result = node.getKey().compareTo(key);
        if (result < 0) {
            return searchNode(node.getRightChild(), key);
        } else if (result > 0) {
            return searchNode(node.getLeftChild(), key);
        } else {
            return node;
        }
    }

    public void inOrderWalk(Consumer<K> consumer) {
        RecursionBinaryTreeWalker.inOrderTraversal(this.root, consumer);
    }
}
